package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-03-08 00:41
 */
public class VerifyPostorder {
    public boolean verifyPostorder(int[] postorder) {

        return verifyPostorder(postorder, 0, postorder.length - 1);

    }

    private boolean verifyPostorder(int[] postorder, int start, int end) {
        if (start >= end) return true;
        int rootVal = postorder[end];
        int r = -1;
        for (int i = end - 1; i >= start; i--) {
            if (rootVal < postorder[i]) continue;
            r = i - 1;
            break;
        }
        for (int i = start; i <=r; i++) {
            if (rootVal<postorder[i]) return false;
        }
        return verifyPostorder(postorder,start,r)&&verifyPostorder(postorder,r+1,end-1);

    }

    public static void main(String[] args) {
        boolean b = new VerifyPostorder().verifyPostorder(new int[]{1,2,5,10,6,9,4,3});
        System.out.println(b);
    }
}
